import java.util.Stack;
/*dp不太好用
* 没有贪心快*/
public class Solution {
    public boolean canJump(int[] nums) {
        int len = nums.length;
        boolean[] dp = new boolean[len];
        dp[len-1] = true;
        for (int i = len-2; i >=0 ; i--) {
            for (int j = 1; j <= nums[i] ; j++) {
                if (dp[i+j]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        if (dp[0]) {
            return true;
        }else {
            return false;
        }
    }

    /*贪心算法*/
    public boolean canJump2(int[] nums) {
        int len = nums.length;
        int maxRight = 0;
        int i = 0;
        while (i <= maxRight) {
            if (i + nums[i] > maxRight) {
                maxRight = i + nums[i];
            }
            if (maxRight >= len - 1) {
                return true;
            }
            i++;
        }

        return false;

    }
}


